home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / dev / lang / SmallEiffel.lha / SmallEiffel / lib_show / knight.e < prev    next >
Text File  |  1998-12-22  |  5KB  |  187 lines
  1. --          This file is part of SmallEiffel The GNU Eiffel Compiler.
  2. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  3. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
  4. --                       http://www.loria.fr/SmallEiffel
  5. -- SmallEiffel is  free  software;  you can  redistribute it and/or modify it 
  6. -- under the terms of the GNU General Public License as published by the Free
  7. -- Software  Foundation;  either  version  2, or (at your option)  any  later 
  8. -- version. SmallEiffel is distributed in the hope that it will be useful,but
  9. -- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. -- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License 
  11. -- for  more  details.  You  should  have  received a copy of the GNU General 
  12. -- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
  13. -- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14. -- Boston, MA 02111-1307, USA.
  15. --
  16. class KNIGHT
  17. --|
  18. --| In this program a knight try to go over the n*n squares of a 
  19. --| chessboard without pass by the same square again.
  20. --| The position of the knigth is given by a number.
  21. --|  
  22. --|  Auteur: Christophe ALEXANDRE
  23. --|  date :  Thu Mar 21 1996
  24. --
  25. -- Here is an example of solution on a 7 X 7 chesboard,
  26. -- knigth starting at position <1,1> :
  27. --                 ----------------------
  28. --                 | 1|28|37|24| 3|26|17|
  29. --                 ----------------------
  30. --                 |36|39| 2|27|18|11| 4|
  31. --                 ----------------------
  32. --                 |29|42|23|38|25|16| 9|
  33. --                 ----------------------
  34. --                 |40|35|30|19|10| 5|12|
  35. --                 ----------------------
  36. --                 |43|22|41|32|15| 8|47|
  37. --                 ----------------------
  38. --                 |34|31|20|45|48|13| 6|
  39. --                 ----------------------
  40. --                 |21|44|33|14| 7|46|49|
  41. --                 ----------------------
  42. --
  43.  
  44. inherit ANY redefine print_on end;
  45.    
  46. creation make
  47.  
  48. feature 
  49.  
  50.    make is
  51.       local
  52.      size, line, column: INTEGER;
  53.       do
  54.      size := ask("Enter the chess-board size : ",3,99);
  55.      line := ask("Enter the start line : ",1,size);
  56.      column := ask("enter the start column : ",1,size);
  57.      knight(size,line,column)
  58.       end;
  59.  
  60. feature {NONE}
  61.  
  62.    chessboard: ARRAY2[INTEGER];
  63.  
  64.    nb_tries: INTEGER;
  65.    
  66.    tl: ARRAY[INTEGER] is 
  67.       once
  68.      Result := <<-2,-1,1,2,2,1,-1,-2>>;
  69.       end;
  70.    
  71.    tc: ARRAY[INTEGER] is
  72.       once
  73.      Result := <<1,2,2,1,-1,-2,-2,-1>>;
  74.       end;
  75.      
  76.    knight(size, line, column: INTEGER) is
  77.       require
  78.      size >= 3;
  79.      1 <= line;
  80.      line <= size;
  81.      1 <= column;
  82.      column <= size;
  83.       do
  84.      !!chessboard.make(1,size,1,size); 
  85.      chessboard.put(1,line,column);
  86.      if solution(line,column) then
  87.         print_on(std_output);
  88.      else
  89.         io.put_string("Sorry, there is no solution.%N");
  90.      end;
  91.      io.put_string("%NNumber of tries : ");
  92.      io.put_integer(nb_tries);
  93.      io.put_new_line;
  94.       end; -- knight
  95.    
  96.    solution(line,column:INTEGER):BOOLEAN is
  97.       local
  98.      value,i : INTEGER;
  99.       do
  100.      if chessboard.count = chessboard.item(line,column) then
  101.         Result := true;
  102.      else
  103.         from  
  104.            i := 1;           
  105.            value := chessboard.item(line,column);
  106.         until
  107.            Result or else i > 8 
  108.         loop
  109.            Result := try(line+tl.item(i),column+tc.item(i),value);
  110.            i := i + 1;
  111.         end;
  112.      end;
  113.       end; -- solution
  114.    
  115.    try(line,column,value:INTEGER): BOOLEAN is
  116.      -- try to place the knight by used cross back-tracking method
  117.       do
  118.      nb_tries := nb_tries + 1;
  119.      if chessboard.valid_index(line,column) then
  120.         if chessboard.item(line,column) = 0 then
  121.            chessboard.put(value+1,line,column);
  122.            Result := solution(line,column);      
  123.            if not Result then
  124.           chessboard.put(0,line,column)
  125.            end;
  126.         end;           
  127.      end
  128.       end; -- try
  129.    
  130.    ask(s:STRING; min, max: INTEGER):INTEGER is 
  131.      -- ask a question until its answer is all right
  132.       local
  133.      stop: BOOLEAN;
  134.       do
  135.      from
  136.      until
  137.         stop
  138.      loop
  139.         io.put_string(s);
  140.         io.read_integer;
  141.         Result := io.last_integer;
  142.         if Result < min then
  143.            io.put_string("Value too small.%N");
  144.         elseif max < Result then
  145.            io.put_string("Value too big.%N");
  146.         else
  147.            stop := true;
  148.         end;
  149.      end;
  150.       end;
  151.       
  152.    print_on(file: OUTPUT_STREAM) is
  153.      -- display the cheesboard 
  154.       local
  155.      line,column : INTEGER;
  156.      separator : STRING;
  157.       do
  158.      from  
  159.         !!separator.blank(3 * chessboard.upper1 + 1);
  160.         separator.fill_with('-');
  161.         separator.extend('%N')
  162.         file.put_string(separator);
  163.         line := chessboard.lower1        
  164.      until
  165.         line > chessboard.upper1
  166.      loop
  167.         from  
  168.            column := chessboard.lower2           
  169.         until
  170.            column > chessboard.upper2
  171.         loop
  172.            if chessboard.item(line,column) < 10 then
  173.           file.put_string("| "); 
  174.            else
  175.           file.put_character('|');
  176.            end;
  177.            file.put_integer(chessboard.item(line,column));
  178.            column := column + 1;
  179.         end;
  180.         file.put_string("|%N");
  181.         file.put_string(separator);
  182.         line := line + 1;
  183.      end;
  184.       end; -- print_on
  185.   
  186. end -- KNIGHT
  187.